Ćwiczenia/4. Ćwiczenia/Zadanie 7. (Podciąg minimalnej długości, zawierający wszystkie k kolorów).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Dana jest tablica $ A $ zawierająca $ n $ elementów, z których każdy ma jeden z k kolorów. Proszę podać możliwie jak najszybszy algorytm, który znajduje indeksy $ i $ oraz $ j $ takie, że wsród elementów $ A[i] $, $ A[i + 1] $, $ ... $ ,$ A[j] $ występują wszystkie $ k $ kolorów oraz wartość $ j − i $ jest minimalna (innymi słowy, szukamy najkrótszego przedziału z wszystkimi kolorami)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Zliczanie kolorów w przedziałach"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ponieważ mamy jawnie daną liczbę różnych kolorów, wynoszącą $ k $, możemy w łatwy sposób sprawdzać, czy dany podciąg tablicy kolorów spełnia warunek taki, że występują w nim wszystkie kolory. Idea jest taka, że będziemy przeglądać tablicę liniowo, przy pomocy dwóch wskaźników, z których pierwszy będzie wyznaczał obecnie sprawdzany element i za razem początek bieżącego podciągu, a drugi koniec tego podciągu. Musimy jeszcze znaleźć taktykę na odpowiednie poruszanie się tymi wskaźnikami oraz wydajne (najlepiej w czasie $ O(1) $) sprawdzanie, czy dany kolor już został uwzględniony. Oczywiście użycie słownika lub zbioru Pythonowego jest zabronione, a to znacznie by nam ułatwiło sprawdzenie. Musimy się więc posłużyć dodatkową tablicą, która będzie przechowywała liczby wystąpień poszczególnych kolorów pod odpowiadającymi danym kolorom indeksami. Zauważmy, że wciąż nie jest to wystarczające, ponieważ chcemy wiedzieć, ile różnych kolorów w tej tablicy się znajduje. Oczywiście można by za każdym razem przebiec całą tablicę liczników kolorów i sprawdzić, czy każdy licznik jest niezerowy (każdy kolor ma przynajmniej jedno wystąpienie), ale nie jest to wydajne rozwiązanie, bo otrzymalibyśmy złożoność obliczeniową całego algorytmu wynoszącą $ O(n \\cdot k) $, a możemy rozwiązać ten problem w czasie $ O(n) $. Wystarczy utworzyć dodatkową zmienną, która będzie zliczała różne kolory w danym przedziale. Zauważmy, że będziemy łatwo w stanie ocenić, czy dany kolor już wystąpił w obecnie sprawdzanym przedziale, ponieważ wystarczy sprawdzić licznik wystąpień bieżącego koloru w tablicy z licznikami (dostęp do odpowiedniej komórki tablicy ma złożoność $ O(1) $) i, jeżeli licznik ten wynosi $ 0 $, inkrementować wartość zmiennej zliczającej liczbę różnych kolorów w przedziale."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Przesuwanie wskaźników"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Musimy jeszcze przemyśleć, jak i kiedy należy poruszyć dany wskaźnik. Ponieważ szukamy przedziału, który ma dokładnie $ k $ ($ k $ to liczba wszystkich kolorów, ale jest dana) różnych kolorów, wystarczy w pętli, odpowiadającej za przemieszczanie pierwszego wskaźnika, sprawdzać, czy zmienna, zliczająca różne kolory (omówiona wyżej), osiągnęła pożądaną wartość równą $ k $. Jeżeli tak, wystarczy sprawdzić, czy długość bieżącego podciągu jest mniejsza od poprzednio zapamiętanej największej długości i zaktualizować tę długość i indeksy najkrótszego przedziału, jeżeli bieżący podciąg jest krótszy od poprzednio zapamiętanego. Pozostaje jeszcze kwestia przemieszczania drugiego wskaźnika. Tutaj najlepiej przyjąć zasadę, że ten wskaźnik możemy ruszyć tylko wtedy, gdy znajduje się on na polu, odpowiadającemu takiemu kolorowi, jak pole, na którym umieszczony został właśnie pierwszy wskaźnik (ponieważ nie potrzebujemy z dwóch stron podciągu tych samych kolorów, tego ostatniego można się pozbyć). Tutaj jeszcze jedna uwaga, a mianowicie w wielu przypadkach przemieszczenie drugiego wskaźnika tylko o jedno pole w prawo może okazać się niewystarczające, bo w bieżącym przedziale wciąż są powtórzone kolory, których możemy się pozbyć (tzn. ten nowo dodany kolor spowodował, że możemy odrzucić nie tylko ten kolor z końca podciągu, ale również kilka takich kolorów, które się powtarzały w tym pociągu). Problem rozwiązuje użycie pętli $ while $ zamiast instrukcji warunkowej i przemieszczanie drugiego wskaźnika do momentu, w którym znajdzie się on na takim kolorze, który występuje w danym przedziale dokładnie jeden raz."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Drobna uwaga na koniec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Warto sobie zdać sprawę, że po osiągnięciu przez naszą zmienną, zliczającą liczbę różnych kolorów w bieżącym podciągu, wartości równej $ k $, wartość tej zmiennej już nigdy nie zostanie zmieniona w żadną stronę, ponieważ zawsze będziemy tak postępować, by nasz przedział zawierał wymaganą liczbę kolorów i odrzucać tylko te kolory, które się powtarzają. Dobrym pomysłem może się więc okazać niesprawdzanie warunku, czy osiągnęliśmy odpowiednią liczbę kolorów w przedziale w każdej pęti. Znacznie lepiej utworzyć osobno pierwszą pętlę, która znajdzie nam pierwszy przedział, w którym występuje dokładnie $ k $ różnych wartości, a następnie już nie sprawdzać tego warunku, a jedynie zmieniać liczby wystąpień odpowiednich kolorów w tablicy z ich licznikami."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Funkcja testująca poprawność algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def test(fn: 'functions which is tested',\n",
    "         k: 'number of unique colors in a subsequence' = None,  # When set to None colors_count will be sued as k\n",
    "         colors_count: 'number of all unique colors' = 5,\n",
    "         arr_length: 'number of array elements (colors)' = (0, 100),\n",
    "         samples: 'number of test repetitions' = 20,\n",
    "         failed_only: 'flag to show or hide output' = False\n",
    "        ):\n",
    "    passed = 0\n",
    "    # Assign colors_count value to k if k is set to None\n",
    "    k = k or colors_count\n",
    "    for test_num in range(1, samples + 1):\n",
    "        # Generate a random array of colors (numbers from 0 to colors_count-1)\n",
    "        arr = [random.randint(0, colors_count-1) for _ in range(random.randint(*arr_length)\n",
    "                                        if not isinstance(arr_length, int) else arr_length)]\n",
    "        if len(arr) < k:\n",
    "            expected = {(None, None)}\n",
    "        else:\n",
    "            # Search for the expected indices of a sequence (this algorithm is simple\n",
    "            # but it runs really slow)\n",
    "            expected = set()\n",
    "            min_length = len(arr)\n",
    "            for i in range(len(arr) - k + 1):\n",
    "                for j in range(i + k, len(arr) + 1):\n",
    "                    if len(set(arr[i:j])) == k:\n",
    "                        curr_length = j - i\n",
    "                        if curr_length < min_length:\n",
    "                            expected = {(i, j - 1)}\n",
    "                            min_length = curr_length\n",
    "                        elif curr_length == min_length:\n",
    "                            expected.add((i, j - 1))\n",
    "                        break\n",
    "            if not expected:\n",
    "                expected.add((None, None))\n",
    "        # Test if an output of our function is correct\n",
    "        result = fn(arr, k, colors_count)\n",
    "        is_correct = result in expected\n",
    "        passed += is_correct\n",
    "        # Show results if not turned off\n",
    "        if not failed_only or (failed_only and not is_correct):\n",
    "            print(f\"TEST #{test_num}:\")\n",
    "            print(f\"Result: i = {result[0]}, j = {result[1]}\")\n",
    "            print(f\"Possible solutions: \\n (i, j) ⋳ {expected}\")\n",
    "            print(f\"Number of unique colors searched: {k}\")\n",
    "            print(f\"Number of unique colors in an array: {colors_count}\")\n",
    "            print(f\"Test {'PASSED' if is_correct else 'FAILED'}\")\n",
    "            print(f\"Current passed-to-test ratio: {passed}/{test_num}\")\n",
    "            print(f\"Input array:\")\n",
    "            print(arr)\n",
    "            print()\n",
    "            \n",
    "    # Print the final results\n",
    "    print(f\"===== Final results: =====\")\n",
    "    print(f\"Total tests passed: {passed}/{samples}\")\n",
    "    print(f\"An algorithm is {'CORRECT' if passed == samples else 'WRONG'}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# I generalize this problem to any k colors value in a subsequence\n",
    "# I assume that colors are represented by positive integers from 0 to colors_count-1 \n",
    "def shortest_k_colors_subsequence(arr: 'array of colors represented by numbers', \n",
    "                                  k: 'number of unique colors in a subsequence',\n",
    "                                  colors_count: 'number of all unique colors'):\n",
    "    # Return None if a number of unique colors is too small\n",
    "    if k < 1 or not arr: return None, None\n",
    "    # Initialize a counters array in order to count occurrences of a color\n",
    "    # within the currently checked range\n",
    "    counters = [0] * colors_count\n",
    "    \n",
    "    # Find the first matching subsequence\n",
    "    i, j = find_first_subseq(arr, k, counters)\n",
    "    # Return None if not found\n",
    "    if i is None: return None, None\n",
    "    \n",
    "    # As we found the first matching subsequence of k unique colors, we can\n",
    "    # begin searching for a possibly shorter one\n",
    "    min_length = j - i + 1\n",
    "    min_i = i\n",
    "    min_j = j\n",
    "    for j in range(j + 1, len(arr)):\n",
    "        counters[arr[j]] += 1\n",
    "        # Move the j pointer till we have repeated colors at the enf of\n",
    "        # our subsequence (use this if and while block in order to check\n",
    "        # if a new subsequence is longer than the previous one only if we\n",
    "        # moved the j pointer (doing so after moving the i pointer is pointless))\n",
    "        if counters[arr[i]] > 1:\n",
    "            counters[arr[i]] -= 1\n",
    "            i += 1\n",
    "            while counters[arr[i]] > 1:\n",
    "                counters[arr[i]] -= 1\n",
    "                i += 1\n",
    "            # Check if a new subsequence is shorter than the previous one\n",
    "            curr_length = j - i + 1\n",
    "            if curr_length < min_length:\n",
    "                min_length = curr_length\n",
    "                min_i = i\n",
    "                min_j = j\n",
    "                \n",
    "    # Return indices of the shorter subsequence which contains all colors\n",
    "    return min_i, min_j\n",
    "\n",
    "\n",
    "def find_first_subseq(arr, k, counters):\n",
    "    # Search fo the first subsequence which contains k different colors\n",
    "    unique_colors = 0\n",
    "    for j in range(len(arr)):\n",
    "        counters[arr[j]] += 1\n",
    "        if counters[arr[j]] == 1:\n",
    "            unique_colors += 1\n",
    "            if unique_colors == k:\n",
    "                break\n",
    "    else:\n",
    "        # If a for loop above hasn't been broken, return None as we are sure\n",
    "        # that unique_colors value is different to the k value\n",
    "        return None, None\n",
    "    \n",
    "    i = 0\n",
    "    # Move the second pointer till we can drop repeated colors\n",
    "    while counters[arr[i]] > 1:\n",
    "        counters[arr[i]] -= 1\n",
    "        i += 1\n",
    "        \n",
    "    return i, j"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "===== Final results: =====\n",
      "Total tests passed: 1000/1000\n",
      "An algorithm is CORRECT\n"
     ]
    }
   ],
   "source": [
    "test(shortest_k_colors_subsequence, samples=1000, failed_only=True)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}